package problem.ej2;

import input.Problem2Input;
import instance.Instance;
import instance.InstanceEj2;

import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import output.Problem2Output;
import output.Problem3Output;
import test.TestEj2;
import test.TestEj3;

public class Problem2 {
	public static long contador_Ej2;
	public static int cant_localidades;
	

	// Red de localidades enlazadas.
	private DistrictNetwork network;

	// �rbol generador m�nimo que representa la soluci�n del problema.
	// Se representa como un conjunto de ejes con sus costos.
	private Set<Link> minimumSpanningTree;

	// Lista de localidades ordenadas.
	private List<Integer> localities;

	public Problem2(List<Link> links) {

		// Obtenemos la cantidad de vertices/localidades.
		Iterator<Link> iterator = links.iterator(); contador_Ej2++;

		localities = new ArrayList(); contador_Ej2++;

		while (iterator.hasNext()) {
			contador_Ej2+=2;
			Link link = (Link) iterator.next();
			if (!localities.contains(new Integer(link.getLoc1()))) {
				localities.add(new Integer(link.getLoc1()));
				contador_Ej2+=2;
			}

			if (!localities.contains(new Integer(link.getLoc2()))) {
				localities.add(new Integer(link.getLoc2()));
				contador_Ej2+=2;
			}
		}

		// Creamos la red con sus datos.
		network = new DistrictNetwork(localities, links);
		contador_Ej2+=2;
		cant_localidades=localities.size();

	}

	// calcula el AGM soluci�n.
	public void computeMinimumSpanningTree() {

		// Inicilaizamos un arbol vac�o
		minimumSpanningTree = new HashSet<Link>(); contador_Ej2+=1;

		// Contaremos que vertices ya han sido generados por las aristas
		// elegidas.
		Set<Integer> treeLocalities = new HashSet<Integer>(); contador_Ej2+=1;
		// Seleccionamos un vertice arbitrariamente.
		treeLocalities.add(new Integer(0)); contador_Ej2+=2;

		Link minLink = null; contador_Ej2+=1;

		// Mientras no hayamos cubierto todos los vertices de la red,
		// seguiremos extendiendo el �rbol.
		while (treeLocalities.size() < localities.size()) {
			contador_Ej2+=2;

			// Buscamos el eje de menor costo tal que expande el arbol desde los
			// vertices ya elegidos.
			minLink = network.findMinAdjacentEdge(treeLocalities);
			contador_Ej2+=1;

			// Verificamos cual de los vertices del nuevo eje extiende el arbol.
			if (treeLocalities.contains(localities.indexOf(minLink.getLoc1()))) {
				treeLocalities.add(localities.indexOf(minLink.getLoc2()));
				contador_Ej2+=2;

			} else {
				treeLocalities.add(localities.indexOf(minLink.getLoc1()));
				contador_Ej2+=localities.size();
				contador_Ej2+=2;
			}

			// Agregamos el nuevo eje al �rbol.
			minimumSpanningTree.add(minLink);
			contador_Ej2+=1; /*El agregar*/
		}

	}
	public static void main(String[] args) throws Exception{
		/*DESCOMENTAR CON CUIDADO: LOS GENERADORES TARDAN MUUUUUUUUUUUCHO*/
//		LinkedList<LinkedList<Link> > completo = TestEj2.generarArbolCompleto(200);
//		LinkedList<LinkedList<Link> > disperso = TestEj2.generarArbolDisperso(200);
//		LinkedList<LinkedList<Link> > denso = TestEj2.generarArbolDenso(200);
//
//		Problem2Output.deListaAArchivo(completo, "./src/resources/Tp2Ej2.completo.sin_repetir.in");
//		Problem2Output.deListaAArchivo(disperso, "./src/resources/Tp2Ej2.disperso.sin_repetir.in");
//		Problem2Output.deListaAArchivo(denso, "./src/resources/Tp2Ej2.denso.sin_repetir.in");
//		TestEj2.repetir_aristas(denso);TestEj2.repetir_aristas(completo);TestEj2.repetir_aristas(disperso);
//		Problem2Output.deListaAArchivo(completo, "./src/resources/Tp2Ej2.completo.repitiendo_aristas.in");
//
//		Problem2Output.deListaAArchivo(disperso, "./src/resources/Tp2Ej2.disperso.repitiendo_aristas.in");
//"./src/resources/Tp2Ej2.disperso.repitiendo_aristas.in");
	
//		Problem2Output.deListaAArchivo(denso, "./src/resources/Tp2Ej2.denso.repitiendo_aristas.in");
		TestEj2.testRendimiento("./src/resources/Tp2Ej2.completo.sin_repetir.in");
		TestEj2.testRendimiento("./src/resources/Tp2Ej2.disperso.sin_repetir.in");
		TestEj2.testRendimiento("./src/resources/Tp2Ej2.denso.sin_repetir.in");
		TestEj2.testRendimiento("./src/resources/Tp2Ej2.completo.repitiendo_aristas.in");
		TestEj2.testRendimiento("./src/resources/Tp2Ej2.denso.repitiendo_aristas.in");
		TestEj2.testRendimiento("./src/resources/Tp2Ej2.disperso.repitiendo_aristas.in");
	}
}
